#include "xutil.h"

#include <random>

//是个闭区间 [minNum,maxNum]
size_t x_next_random(size_t minNum, size_t maxNum)
{
    static std::random_device rd;
    static std::mt19937 gen(rd());
    std::uniform_int_distribution<> dis(minNum, maxNum);

    return dis(gen);
}

size_t x_next_random(size_t maxNum)
{
    return x_next_random(0, maxNum);
}

size_t x_gcd(size_t a, size_t b)
{
    if (b == 0) {
        return a;
    }
    return x_gcd(b, a % b);
}

int mod(int a, int m)
{
    int r = a % m;
    return r < 0 ? r + m : r; // 若余数为负，加上模数 m
}

int safe_mod(int a, int m)
{
    return (a % m + m) % m;
}

// 扩展欧几里得算法（迭代版）非递归
//int extended_gcd(int a, int b, int &x, int &y) {
//    x = 1, y = 0;
//    int x1 = 0, y1 = 1; // 初始化系数
//    while (b != 0) {
//        int q = a / b;
//        tie(x, x1) = make_tuple(x1, x - q * x1);
//        tie(y, y1) = make_tuple(y1, y - q * y1);
//        tie(a, b) = make_tuple(b, a - q * b);
//    }
//    return a; // 返回 gcd(a, b)
//}

//int mod_inverse(int a, int m) {
//    int x, y;
//    int gcd = extended_gcd(a, m, x, y);
//    if (gcd != 1) {
////        cerr << "逆元不存在！" << endl;
//        return -1;
//    } else {
//        return (x % m + m) % m; // 调整到 [0, m-1]
//    }
//}

// 扩展欧几里得算法（递归版）
// 返回 gcd(a, b)，并更新 x 和 y 使得 ax + by = gcd(a, b)
//int extended_gcd(int a, int b, int &x, int &y) {
//    if (b == 0) {
//        x = 1;
//        y = 0;
//        return a;
//    }
//    int gcd = extended_gcd(b, a % b, x, y);
//    int temp = x;
//    x = y;
//    y = temp - (a / b) * y;
//    return gcd;
//}

//// 计算模逆元（a^{-1} mod m）
//int mod_inverse(int a, int m) {
//    int x, y;
//    int gcd = extended_gcd(a, m, x, y);
//    if (gcd != 1) {
////        cerr << "逆元不存在，因为 a 和 m 不互质！" << endl;
//        return -1; // 无逆元
//    } else {
//        // 调整 x 为正数
//        return (x % m + m) % m;
//    }
//}

mpn::cpp_int extended_gcd(mpn::cpp_int a, mpn::cpp_int b, mpn::cpp_int &x, mpn::cpp_int &y)
{
    if (b == 0) {
        x = 1;
        y = 0;
        return a;
    }
    mpn::cpp_int gcd = extended_gcd(b, a % b, x, y);
    mpn::cpp_int temp = x;
    x = y;
    y = temp - (a / b) * y;
    return gcd;
}

// 计算模逆元（a^{-1} mod m）
mpn::cpp_int mod_inverse(mpn::cpp_int a, mpn::cpp_int m)
{
    mpn::cpp_int x, y;
    mpn::cpp_int gcd = extended_gcd(a, m, x, y);
    if (gcd != 1) {
        std::cerr << "逆元不存在，因为 a 和 m 不互质！" << std::endl;
        return -1; // 无逆元
    } else {
        // 调整 x 为正数
        return (x % m + m) % m;
    }
}

// 快速模幂计算 (a^b mod m)
//long long fast_mod_exp(long long a, long long b, long long m) {
//    long long res = 1;
//    a = a % m; // 初始取模，防止溢出
//    while (b > 0) {
//        if (b & 1) { // 如果当前位是1
//            res = (res * a) % m;
//        }
//        a = (a * a) % m; // a 平方
//        b = b >> 1; // b 右移一位
//    }
//    return res;
//}

mpn::cpp_int fast_mod_exp(mpn::cpp_int a, mpn::cpp_int b, mpn::cpp_int m)
{
    mpn::cpp_int res = 1;
    a = a % m; // 初始取模，防止溢出
    while (b > 0) {
        if (b & 1) { // 如果当前位是1
            res = (res * a) % m;
        }
        a = (a * a) % m; // a 平方
        b = b >> 1;      // b 右移一位
    }
    return res;
}
